Partition Array into Disjoint Intervals

LeetCode 951 | Difficulty: Medium

Medium

Problem Description

Given an integer array nums, partition it into two (contiguous) subarrays left and right so that:

• Every element in left is less than or equal to every element in right.

• left and right are non-empty.

• left has the smallest possible size.

Return the length of left after such a partitioning.

Test cases are generated such that partitioning exists.

Example 1:

Input: nums = [5,0,3,8,6]
Output: 3
Explanation: left = [5,0,3], right = [8,6]

Example 2:

Input: nums = [1,1,1,0,6,12]
Output: 4
Explanation: left = [1,1,1,0], right = [6,12]

Constraints:

• 2 <= nums.length <= 10^5

• 0 <= nums[i] <= 10^6

• There is at least one valid answer for the given input.

Topics: Array

---

Solutions

Solution 1: C# (Best: 369 ms)

Metric	Value
Runtime	369 ms
Memory	49.3 MB
Date	2022-02-05

Solution

public class Solution {
    public int PartitionDisjoint(int[] nums) {
        int curmax = nums[0];
        int nxtmax = nums[0];
        int disjoint = 0;
        for(int i=1;i<nums.Length;i++)
        {
            nxtmax = Math.Max(nxtmax, nums[i]);
            if(nums[i]<curmax)
            {
                curmax = nxtmax;
                disjoint = i;
            }
        }
        return disjoint+1;
    }
}

---

Complexity Analysis

Approach	Time	Space
Solution	$O(n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.